//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "iterator_traits.h"


// heap.h
//
// Implements a standard binary heap structure using random-access and sequential data.
// Binary heaps generally have an overall excellent worst-case of O(n log n).
// *Note* (This is very close to reference implementation and not optimized in any meaningful way.)
// 
//      [0]
//     /   \
//   [1]   [2]
//   / \ 
// [3] [4]
//
//
// make_heap
// push_heap
// pop_heap
// is_heap
// is_heap_until
// sort_heap
// heap_sort
// partial_sort
// partial_sort_copy

FC_NAMESPACE_BEGIN


namespace internal
{
	template <class RandomAccessIterator, class T, class Compare> inline
	void promote_heap( RandomAccessIterator first, size_t hole, size_t top, const T& value, Compare compare )
	{
		size_t parent = (hole - 1) >> 1;
		while( hole > top && compare(first[parent], value) )
		{
			first[hole] = first[parent];
			hole = parent;
			parent = (parent - 1) >> 1;
		}

		first[hole] = value;
	}

	template <class RandomAccessIterator, class T> inline
	void promote_heap( RandomAccessIterator first, size_t hole, size_t top, const T& value )
	{
		size_t parent = (hole - 1) >> 1;
		while( hole > top && first[parent] < value )
		{
			first[hole] = first[parent];
			hole = parent;
			parent = (parent - 1) >> 1;
		}

		first[hole] = value;
	}

	template <class RandomAccessIterator, class T, class Compare> inline
	void adjust_heap( RandomAccessIterator first, const size_t heapSize, size_t hole, const T& value, Compare compare ) 
	{
		size_t child = hole * 2 + 2;
		size_t top = hole;

		while( child < heapSize )
		{
			if( compare(first[child], first[child - 1]) )
				child--;
			first[hole] = first[child];
			hole = child;
			child = child * 2 + 2;
		}

		if( child == heapSize )
		{
			first[hole] = first[child - 1];
			hole = child - 1;
		}

		promote_heap<RandomAccessIterator, T, Compare>( first, hole, top, value, compare );
	}

	template <class RandomAccessIterator, class T> inline
	void adjust_heap( RandomAccessIterator first, const size_t heapSize, size_t hole, const T& value ) 
	{
		size_t child = hole * 2 + 2;
		size_t top = hole;

		while( child < heapSize )
		{
			if( first[child] < first[child - 1] )
				child--;
			first[hole] = first[child];
			hole = child;
			child = child * 2 + 2;
		}

		if( child == heapSize )
		{
			first[hole] = first[child - 1];
			hole = child - 1;
		}

		promote_heap<RandomAccessIterator, T>( first, hole, top, value );
	}

} //internal


// make_heap

template <class RandomAccessIterator, class Compare> inline
	void make_heap( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		const size_t heapSize = size_t(last - first);
		if( heapSize > 1 )
		{
			for( size_t parent = (heapSize >> 1) - 1; ; --parent )
			{
				typedef typename fc::iterator_traits<RandomAccessIterator>::value_type value_type;
				const value_type temp(first[parent]);

				// heapify values by traversing downwards to the bottom.
				internal::adjust_heap<RandomAccessIterator, value_type, Compare>( first, heapSize, parent, temp, compare ); 
				if( parent == 0 )
					break;
			}
		}
	}

template <class RandomAccessIterator>
	void make_heap( RandomAccessIterator first, RandomAccessIterator last )
	{
		const size_t heapSize = size_t(last - first);
		if( heapSize > 1 )
		{
			for( size_t parent = (heapSize >> 1) - 1; ; --parent )
			{
				typedef typename fc::iterator_traits<RandomAccessIterator>::value_type value_type;
				const value_type temp(first[parent]);

				// heapify values by traversing downwards to the bottom.
				internal::adjust_heap<RandomAccessIterator, value_type>( first, heapSize, parent, temp ); 
				if( parent == 0 )
					break;
			}
		}
	}


// push_heap

template <class RandomAccessIterator, class Compare>
	void push_heap( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		const size_t heapSize = size_t(last - first - 1);

		typedef typename fc::iterator_traits<RandomAccessIterator>::value_type value_type;
		const value_type temp(first[heapSize]);

		// use previous heapsize of [first. last-1) and trickle upwards from bottom, placing value.
		internal::promote_heap<RandomAccessIterator, value_type, Compare>( first, heapSize, 0, temp, compare );
	}

template <class RandomAccessIterator>
	void push_heap( RandomAccessIterator first, RandomAccessIterator last )
	{
		const size_t heapSize = size_t(last - first - 1);

		typedef typename fc::iterator_traits<RandomAccessIterator>::value_type value_type;
		const value_type temp(first[heapSize]);

		// use previous heapsize of [first. last-1) and trickle upwards from bottom, placing value.
		internal::promote_heap<RandomAccessIterator, value_type>( first, heapSize, 0, temp );
	}


// pop_heap

template <class RandomAccessIterator, class Compare> inline
	void pop_heap( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		FC_ASSERT(first != last);

		// swap bottom with value, pop last, and adjust the heap.
		typedef typename fc::iterator_traits<RandomAccessIterator>::value_type value_type;
		const value_type temp(*(--last));
		*last = *first;

		internal::adjust_heap<RandomAccessIterator, value_type, Compare>( first, size_t(last - first), 0, temp, compare );
	}

template <class RandomAccessIterator>
	void pop_heap( RandomAccessIterator first, RandomAccessIterator last )
	{
		FC_ASSERT(first != last);

		// swap bottom with value, pop last, and adjust the heap.
		typedef typename fc::iterator_traits<RandomAccessIterator>::value_type value_type;
		const value_type temp(*(--last));
		*last = *first;

		internal::adjust_heap<RandomAccessIterator, value_type>( first, size_t(last - first), 0, temp );
	}


// is_heap_until

template <class RandomAccessIterator, class Compare>
	RandomAccessIterator is_heap_until( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		int i = 0;
		for( RandomAccessIterator child = first + 1; child < last; ++child, ++i )
		{
			if( compare(*first, *child) )
				return child;
			if( (i & 1) != 0 )
				++first;
		}

		return last;
	}

template <class RandomAccessIterator>
	RandomAccessIterator is_heap_until( RandomAccessIterator first, RandomAccessIterator last )
	{
		int i = 0;
		for( RandomAccessIterator child = first + 1; child < last; ++child, ++i )
		{
			if( *first < *child )
				return child;
			if( (i & 1) != 0 )
				++first;
		}

		return last;
	}


// is_heap

template <class RandomAccessIterator, class Compare>
	bool is_heap( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		return is_heap_until<RandomAccessIterator, Compare>(first, last) == last;
	}

template <class RandomAccessIterator>
	bool is_heap( RandomAccessIterator first, RandomAccessIterator last )
	{
		return is_heap_until<RandomAccessIterator>(first, last) == last;
	}


// sort_heap

template <class RandomAccessIterator, class Compare>
	void sort_heap( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		for( ; first != last; --last )
			pop_heap<RandomAccessIterator, Compare>( first, last, compare );
	}

template <class RandomAccessIterator>
	void sort_heap( RandomAccessIterator first, RandomAccessIterator last )
	{
		for( ; first != last; --last )
			pop_heap<RandomAccessIterator>( first, last );
	}


// heap_sort

template <class RandomAccessIterator, class Compare> inline
	void heap_sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		make_heap<RandomAccessIterator, Compare>( first, last, compare );
		sort_heap<RandomAccessIterator, Compare>( first, last, compare );
	}

template <class RandomAccessIterator> inline
	void heap_sort( RandomAccessIterator first, RandomAccessIterator last )
	{
		make_heap<RandomAccessIterator>( first, last );
		sort_heap<RandomAccessIterator>( first, last );
	}


// partial_sort

template <class RandomAccessIterator, class Compare> inline
	void partial_sort( RandomAccessIterator first, RandomAccessIterator mid, RandomAccessIterator last, Compare compare )
	{
		make_heap<RandomAccessIterator, Compare>( first, mid, compare );

		for( RandomAccessIterator i = mid; i != last; ++i )
		{
			if( compare(*i, *first) )
			{
				// iterate through the remaining range and simply pop the max heap with the value at 'next'
				// and place it at at the current position in the unsorted range [mid, last).

				typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
				const value_type temp(*i);
				*i = *first;

				internal::adjust_heap<RandomAccessIterator, value_type, Compare>( first, size_t(mid - first), 0, temp, compare );
			}
		}

		sort_heap<RandomAccessIterator, Compare>( first, mid, compare );
	}

template <class RandomAccessIterator> inline
	void partial_sort( RandomAccessIterator first, RandomAccessIterator mid, RandomAccessIterator last )
	{
		make_heap<RandomAccessIterator>( first, mid );

		for( RandomAccessIterator i = mid; i != last; ++i )
		{
			if( *i < *first )
			{
				typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
				const value_type temp(*i);
				*i = *first;

				internal::adjust_heap<RandomAccessIterator, value_type>( first, size_t(mid - first), 0, temp );
			}
		}

		sort_heap<RandomAccessIterator>( first, mid );
	}


// partial_sort_copy

template <class InputIterator, class RandomAccessIterator, class Compare> inline
	RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last,
	RandomAccessIterator resultFirst, RandomAccessIterator resultLast, Compare compare )
	{
		RandomAccessIterator resultMid = resultFirst;
		while( first != last && resultMid != resultLast )
		{
			*resultMid = *first;
			++first;
			++resultMid;
		}

		typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
		typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
		const difference_type n = difference_type(resultMid - resultFirst);

		make_heap<RandomAccessIterator, Compare>( resultFirst, resultMid, compare );

		for( ; first != last; ++first )
		{
			if( compare(*first, *resultFirst) )
			{
				const value_type temp(*first);
				internal::adjust_heap<RandomAccessIterator, value_type, Compare>( resultFirst, n, 0, temp, compare );
			}
		}

		sort_heap<RandomAccessIterator, Compare>( resultFirst, resultMid, compare );
		return resultMid;
	}

template <class InputIterator, class RandomAccessIterator> inline
	RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last,
	RandomAccessIterator resultFirst, RandomAccessIterator resultLast )
	{
		RandomAccessIterator resultMid = resultFirst;
		while( first != last && resultMid != resultLast )
		{
			*resultMid = *first;
			++first;
			++resultMid;
		}

		typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
		typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
		const difference_type n = difference_type(resultMid - resultFirst);

		make_heap<RandomAccessIterator>( resultFirst, resultMid );

		for( ; first != last; ++first )
		{
			if( *first < *resultFirst )
			{
				const value_type temp(*first);
				internal::adjust_heap<RandomAccessIterator, value_type>( resultFirst, n, 0, temp );
			}
		}

		sort_heap<RandomAccessIterator>( resultFirst, resultMid );
		return resultMid;
	}




FC_NAMESPACE_END
